#include "ApproximateMedian.h"
#include <vector>
#include <algorithm>

ApproximateMedian::ApproximateMedian(){

}

ApproximateMedian::ApproximateMedian(int d)
{
    mpi = new double[D];
}
//Constructor for ApproxiMedian class
//Takes total number of records (tr) and total number of dimensions (d) as input and
//assigns number of dimensions to variables
ApproximateMedian::ApproximateMedian(int tr, int d){
    totalrecords = tr;
    D=d;
    array_data = new double[totalrecords*D];
    data = new double*[totalrecords];
    for (int i = 0; i < totalrecords; ++i)
    data[i] = array_data + D*i;
    mpi = new double[D];
}

void ApproximateMedian::setmedian(double* m)
{
    mpi = m;
}

//A function to intialize variables
void ApproximateMedian::initialize(int tr, int d, double** val){
    totalrecords = tr;
    D=d;
    array_data = new double[totalrecords*D];
    data = new double*[totalrecords];
    for (int i = 0; i < totalrecords; ++i)
    data[i] = array_data + D*i;
    mpi = new double[D];
    data = val;
}

//A function to assign data
void ApproximateMedian::set_data(double **d){
    data = d;
}

double ApproximateMedian::getmedian(int d)
{
    return mpi[d];
}

void ApproximateMedian::set(int i, double value)
{
	mpi[i] = value;
}
//A function to find approximate median, by using histogram. Function assumes, data value is in range 0.0-1.0
//Calculates approximate median value in each dimension, by binning the data records in each dimension
double * ApproximateMedian::findapproximatemedians(){

    for(int j=0; j< D; j++)
    {
        //Maintains count of values in the follwing range
        // [value >=0 && value <=0.1][value >0.1 && value <=0.2][value >0.2 && value <=0.3]
        // [value >0.3 && value <=0.4][value >0.4 && value <=0.5][value >0.5 && value <=0.6]
        // [value >0.6 && value <=0.7][value >0.7 && value <=0.8][value >0.8 && value <=0.9]
        // [value >0.9 && value <=1.0]
        double fc[10];    
        for(int i=0; i< 10; i++){
            fc[i] = 0;
        }
        //Location of median value
        double medianrecord = totalrecords/2;
        //Count of records
        double countofrecords=0;
        //Remianing number of values need to reach media location
        double remnovalue=0;
        //Number of records needed from next bin, to reach median location
        double perofremval=0;
        for(int i=0; i< totalrecords; i++)
        {
            if(data[i][j] >=0 && data[i][j] <=0.1) fc[0] = fc[0]+1; 
            if(data[i][j] >0.1 && data[i][j] <=0.2) fc[1] = fc[1]+1;
            if(data[i][j] >0.2 && data[i][j] <=0.3) fc[2] = fc[2]+1;
            if(data[i][j] >0.3 && data[i][j] <=0.4) fc[3] = fc[3]+1;
            if(data[i][j] >0.4 && data[i][j] <=0.5) fc[4] = fc[4]+1;
            if(data[i][j] >0.5 && data[i][j] <=0.6) fc[5] = fc[5]+1;
            if(data[i][j] >0.6 && data[i][j] <=0.7) fc[6] = fc[6]+1;
            if(data[i][j] >0.7 && data[i][j] <=0.8) fc[7] = fc[7]+1;
            if(data[i][j] >0.8 && data[i][j] <=0.9) fc[8] = fc[8]+1;
            if(data[i][j] >0.9 && data[i][j] <=1.0) fc[9] = fc[9]+1;
        }
        //To find whether medain has been determined
        bool medianfound = false;
        for(int k=0; k< 10 && !medianfound; k++)
        {
            if(countofrecords + fc[k] <= medianrecord){
            countofrecords = countofrecords + fc[k];
            }
            else{
             
                remnovalue = medianrecord - countofrecords;
         
                switch(k){
                    case 0: perofremval = (remnovalue/fc[k] )/10; remnovalue = 0.0 + perofremval; medianfound=true; break;
                    case 1: perofremval = (remnovalue/fc[k] )*0.09; remnovalue = 0.1 + perofremval; medianfound=true; break;
                    case 2: perofremval = (remnovalue/fc[k] )*0.09; remnovalue = 0.2 + perofremval; medianfound=true; break;
                    case 3: perofremval = (remnovalue/fc[k] )*0.09; remnovalue = 0.3 + perofremval; medianfound=true; break;
                    case 4: perofremval = (remnovalue/fc[k] )*0.09; remnovalue = 0.4 + perofremval; medianfound=true; break;
                    case 5: perofremval = (remnovalue/fc[k] )*0.09; remnovalue = 0.5 + perofremval; medianfound=true; break;
                    case 6: perofremval = (remnovalue/fc[k] )*0.09; remnovalue = 0.6 + perofremval; medianfound=true; break;
                    case 7: perofremval = (remnovalue/fc[k] )*0.09; remnovalue = 0.7 + perofremval; medianfound=true; break;
                    case 8: perofremval = (remnovalue/fc[k] )*0.09; remnovalue = 0.8 + perofremval; medianfound=true; break;
                    case 9: perofremval = (remnovalue/fc[k] )*0.09; remnovalue = 0.9 + perofremval; medianfound=true; break;
                }
               
                
            }
        }
        //Assign median value to the corresponding dimension
        mpi[j]=remnovalue;

    }


    return mpi;
}

//A function that performs data transformation, based on Pyramid Technique paper
//See paper, for details
double * ApproximateMedian::convertdatapoint(double values[]){

    double *convertedvalues= new double [D];

    for(int i=0; i< D; i++){
        double lgx = log2(mpi[i]);

        double r = (1/lgx) * -1;
        convertedvalues[i]=pow(values[i],r);
    }

    return convertedvalues;
}

double** ApproximateMedian::convertqueryrange(double q[][2]){
    double** convertedq;
    double * a_data;
    
    a_data = new double[D*2];
    convertedq = new double*[D];
    
    for (int i = 0; i < D; ++i)
    	convertedq[i] = a_data + 2*i;

    

    for(int i=0; i< D; i++){

        for(int j=0; j< 2; j++){
            double lgx = log2(mpi[i]);

            double r = (1/lgx) *-1;

            convertedq[i][j]=pow(q[i][j],r);

          
        }
    }

    

    return convertedq;
    
}

//This function moves the median of a triplet of terms at location A[i],
//A[j], A[k] to the middle position
void ApproximateMedian::triplet_adjust(double A[], int i, int Step){
    double swap1(0), swap2(0);
    
    int j = i + Step; int k = i+2-Step;
    if(A[i] < A[j]){
        if(A[k]<A[i]){
            swap1 = A[i];
            swap2 = A[j];
            A[i]=swap2;
            A[j]=swap1;
        }else if(A[k]<A[j]){
            swap1=A[j];
            swap2 = A[k];
            A[j]=swap2;
            A[k]=swap1;
        }
    }else {
        if(A[i]<A[k]){
            swap1 = A[i];
            swap2 = A[j];
            A[i]=swap2;
            A[j]=swap1;
        }else if(A[k]>A[j]){
            swap1=A[j];
            swap2 = A[k];
            A[j]=swap2;
            A[k]=swap1;
        }
    }

}

//This function sorts Size elements of the array A located at positions Left, Left+Step,
//Left+2*Step.....
void ApproximateMedian::selection_sort(double A[], int Left, int Size, int Step){
    int min=0;
    double swap1(0), swap2(0);
    for(int i=Left; i<Left + (Size-1)*Step; i= i + Step){
        min = i;
        for(int j= i + Step; j< Left + Size*Step; j = j+ Step){
            if(A[j] < A[min]){
                min = j;
            }
        }
        swap1 = A[i];
        swap2 = A[min];
        A[i]=swap2;
        A[min]=swap1;


    }
}


//This function returns the approximate median of the array A[0,...,Size-1]
double ApproximateMedian::approximate_median_anyN(double A[], int Size){
    bool LeftToRight=false;
    int Threshold(50);
    int Left(0),Step(1),Rem(0),i(0);
    double swap1(0),swap2(0);
 
    while(Size>Threshold){
        LeftToRight = !(LeftToRight);
        Rem = Size % 3;
        if(LeftToRight){
            i = Left;
        }else{
            i=Left + (3+Rem)*Step;
        }

        

         
        
         for(int h=0; h<(Size/3)-1; h++)
         {
            triplet_adjust(A,i,Step);
            
            i=i+3*Step;
           

        }

        if(LeftToRight){
            Left = Left + Step;
        }else{
            i=Left;
            Left=Left+(1+Rem)*Step;
        }

        selection_sort(A,i,3+Rem,Step);
           

        if(Rem==2){
            if(LeftToRight){
                swap1 = A[i+Step];
                swap2 = A[i+2*Step];
                A[i+Step]=swap2;
                A[i+2*Step]=swap1;
            }else{
                swap1 = A[i+2*Step];
                swap2 = A[i+3*Step];
                A[i+2*Step]=swap2;
                A[i+3*Step]=swap1;
            }
        }

        Step=3*Step; Size=Size/3;
     

    }

    
    selection_sort(A,Left,Size,Step);

    
    return A[Left+Step* ((Size-1)/2)];

}

//A function to calculated median for each dimension in the given data
//using function approximate_median_anyN
double * ApproximateMedian::findapproximatemediansusingAMN(){
    
    for(int j=0; j<D; j++){
       
        double A[totalrecords];
        
        for(int i=0; i<totalrecords; i++){
            A[i]=data[i][j];
        }
        
        mpi[j]=approximate_median_anyN(A, totalrecords);
        
    }

    return mpi;
}

double * ApproximateMedian::findmedian()
{
    for(int j=0; j<D; j++)
    {
		//set up for odd number of points
		bool medSplit = false;
		int m = (totalrecords / 2);
		int m2 = -1; //not used for odd

		if(totalrecords % 2 == 0) //if even number of points
		{
		medSplit = true;
		m = (totalrecords / 2) - 1;
		m2 = (totalrecords / 2);
		}

		vector<double> points;



		for(int i = 0; i < totalrecords; i++)
		{
		  //add each point's ith value to the vector
		  points.push_back(  data[i][j] );

		}

		//sort points vector
		sort(points.begin(), points.end());

		if(medSplit)
		{
		  //average of the two middle points
		  mpi[j] = (points[m] + points[m2]) / 2.0;
		}
		else
		{
		  mpi[j] = points[m];
		}

    }


    return mpi;
}



